function quickSort(arr, startIndex, endIndex) {
  //递归结束条件：startIndex大于或等于endIndex
  if (startIndex >= endIndex) {
    return;
  }
  //得到基准元素位置
  let pivotIndex = partition(arr, startIndex, endIndex);
  //根据基准元素，分成两部分进行递归排序
  quickSort(arr, startIndex, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, endIndex);
}
/**
 * 分支 单边循环法
 * @param {*} arr 
 * @param {*} startIndex 
 * @param {*} endIndex 
 * @returns 
 */
function partition(arr, startIndex, endIndex) {
  //取第1个位置的元素作为基准元素
  let pivot = arr[startIndex];
  // mark记录比基准元素小的元素的位置
  let mark = startIndex;
  for (let i = startIndex + 1; i <= endIndex; i++) {
    if (arr[i] < pivot) {
      mark++;
      let p = arr[mark];
      arr[mark] = arr[i];
      arr[i] = p;
    }
  }
  arr[startIndex] = arr[mark];
  arr[mark] = pivot;
  return mark;
}
let arr = [4, 4, 6, 5, 3, 2, 8, 1];
quickSort(arr, 0, arr.length - 1);
console.log(arr);